package tree.leetcode_113_medium_backtrace;

import java.util.ArrayList;
import java.util.List;

public class BackTrace {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        List<Integer> list = new ArrayList<>();
        dfs(root, sum, list, res);
        return res;
    }

    public void dfs(TreeNode root, int target, List<Integer> path, List<List<Integer>> res) {
        if (root == null) {
            return;
        }
        //记录当前的路径值
        path.add(root.val);
        //到达叶子结点，并且找到目标值
        if (root.left == null && root.right == null && target - root.val == 0) {
            //引用类型，path 集合会在递归过程中被不断改变，所以此时需要new一个来保存此时 path 的结果。
            res.add(new ArrayList<>(path));
            //“剪枝”，在回溯之前进行剪枝操作，防止分支污染。
            path.remove(path.size() - 1);
            return;
        }
        //左子树寻找目标值
        dfs(root.left, target - root.val, path, res);
        //右子树寻找目标值
        dfs(root.right, target - root.val, path, res);
        //回溯之前进行“剪枝”
        path.remove(path.size() - 1);
        return;
    }
}
